/*****************************************************************************
 *Name: Stephen Durfey
 *Class: cs335
 *Prof: Dr. Michael Poor
 *Due: October 13, 2008
 *Description: finds the secret combination of the vault by looking for clues
 *             throughout 4 seperate linked list.
 *
 *****************************************************************************/


#include <iostream>
#include <list>
#include <cstdlib>


using namespace std;
const int messageSize = 5;
const char message2[] = {'L','i','n','k','y'};
const string message1[] = {"You'll", "never", "see", "him", "again"};


void initialize(list<string> &first, list<char> &second, list<int> &third, list<unsigned long> &fourth)
{
	//create 5 string links in first
	for(int i=0; i < messageSize; i++)
	{
		first.push_front(message1[rand()%5]);
	}
	
	//iterate and add linking at rand2 location
	for(int i = 0; i < messageSize; i++)
	{
		second.push_front(message2[i]);
		second.push_back(message2[i]);
	}
	
	//put random ints in the thrid list
	for(int i = 0; i < messageSize*2; i++)
	{
		third.push_front(rand()%100);
	}

	//put random longs in the last list
	for(int i = 0; i < 100; i++)
	{
		fourth.push_front( (unsigned long) rand()*123456789+100000000 );
	}

}

void kidnap(list<string> &stringList)
{
	//hide linky in list by iterating through the begining of the list
	//and setting the node at a random location to the string "Linky"

	//First get the size of the list, call it size
	//Second get a random location within that size

	int size = stringList.size();
	int location = rand()%size;
	list<string>::iterator itr = stringList.begin();

	while(location > 0) {
		itr++;
		location--;
	}

	//The insert function
	list<string>::iterator itr2;
	itr2 = stringList.insert(itr, "Linky");
}

unsigned long search(list<string> &first, list<char> &second, list<int> &third, list<unsigned long> &fourth)
{
    list<string>::iterator stringIter = first.begin();
    int linkyPosition = 0;
    char toFind;
    
    //loops until "Linky" is found and stores the corresponding index value
    //of message2[] to 'toFind';
    while(*stringIter != "Linky")
    {
        stringIter++;
        linkyPosition++;
    }
    
    toFind = message2[linkyPosition];
    
    //---------------------------------------------------------------------
    //finds integer of corresponding index of fourth to find combo
    
    list<char>::iterator charIter = second.begin();
    int foundCharPos = 0, iters = 0;
    
    //loops through entire list finding the last position of the char 'toFind'
    //stores it in 'iters'. 'iters' serves as the loop control variable (LCV), to 
    //find the corresponding int value 'iters' times from the end of list.
    while(foundCharPos < second.size())
    {
        if(*charIter == toFind)
            iters = foundCharPos;
        
        foundCharPos++;
        charIter++;
    }
    
    //------------------------------------------------------------------
    //finds the integer value 'iters' times from the end of the list. serves
    //as the 'foundValue' largest number in the fourth list.
    list<int>::iterator intIter = third.end();
    int foundValue;
    
    for(int index = 0; index < iters; index++, intIter--)
        ;
    foundValue = *intIter;
    
    //----------------------used to find combo-------------------------
    //used to find the "foundValue" highest number in the list
    
    list<unsigned long>::iterator longIter = fourth.begin();
    unsigned long int combo;
    
    fourth.sort(); //sorts list in ascending order
    for(int index = 0; index < foundValue; index++, longIter++)
        ;
    
    combo = *longIter;
    return combo;
} 
    
int main() {
	
	//create four lists
	list<string> stringList;
	list<char> charList;
	list<int> intList;
	list<unsigned long> longList;
	
	//use this function to initialize all of them
	initialize(stringList, charList, intList, longList);

	//create an iterator for each list
	list<string>::iterator itS;
	list<char>::iterator itC;
	list<int>::iterator itI;
	list<unsigned long>::iterator itL;
	
	//answer
	unsigned long combination;
	
	//kidnap linky
	kidnap(stringList);
	
	
	//PRINT THE LISTS
	
	for (itS=stringList.begin(); itS!=stringList.end(); itS++) { 
			cout << " " << *itS;
	}
	
	cout << endl;

	for (itC=charList.begin(); itC!=charList.end(); itC++) {
		cout << " " << *itC;
	}
	
	cout << endl;
	
	for (itI=intList.begin(); itI!=intList.end(); itI++) {
		cout << " " << *itI;
	}
	
	cout << endl;
	
	for (itL=longList.begin(); itL!=longList.end(); itL++) {
		cout << " " << *itL;
	}
	cout << endl;

	//here is the answer
	combination = search(stringList, charList, intList, longList);
	cout << "The code for the safe deposit box is: " << combination << endl;

	return 0;
}
